// NextUseRegAllocator.cpp 
// Implement class NextUseRegAllocator
#include "crossbit/NextUseRegAllocator.h"
#include "crossbit/VBlock.h"
#include "crossbit/VInst.h"

using namespace crossbit;

void NextUseRegAllocator::init(VBlock *vb)
{
	vinst_seq = 0;

	for( XTRegNum i = 0 ; i < ra_num_of_reg ; ++i ){
		ra_reg_table[i].status = RegAllocator::FREE;
	}

	for( XTInt32 i = 0 ; i < MAX_VREG_NUM ; i++ ){
		while( !ra_vreg_used_list[i].empty() ){
			ra_vreg_used_list[i].pop();
		}
	}
	UTIL::XTMemset( ra_vreg_spilled , 0 , sizeof( ra_vreg_spilled ) ); 
	collectNextUseInfo(vb);
}

void NextUseRegAllocator::phaseTask()
{

}

void NextUseRegAllocator::collectNextUseInfo(VBlock *vb)
{
	XTUint32 seq = 0;

	VBlock::vb_const_iterator it = vb -> begin();
	VBlock::vb_const_iterator end = vb -> end();

	for( ; it != end ; it++ , seq++ ){
		VInst *inst = *it;
		XTUint32 n = inst->getOperandNum();

		for (XTInt32 i = 1; i <= n; i++ )
		{
			Operand opr = inst->getOperand(i);
			XTRegNum r;

			if (opr.type == Operand::VREG_USE || opr.type == Operand::VREG_DEF)
			{ 
				if (opr.type == Operand::VREG_USE)
				{
					r = opr.reg;
					ra_vreg_used_list[r].push(std::make_pair(seq,USE));
				}

				if (opr.type == Operand::VREG_DEF)
				{
					r = opr.reg;
					ra_vreg_used_list[r].push(std::make_pair(seq,DEF));
				}
			}
		}
	}
}

// this is a auxilary function used for debugging
void NextUseRegAllocator::printNextUseInfo()
{

}

// Allocate target register for virtual register
XTRegNum NextUseRegAllocator::regAlloc(XTRegNum vreg, RegAccessMode mode)
{
	//printf("This is regAlloc calling!\n");
	XTRegNum alloc = ra_num_of_reg;
	for( XTRegNum i = 0 ; i < ra_num_of_reg ; i++ ){
		if( ra_reg_table[i].status == ALLOCATED && ra_reg_table[i].mapped_to == vreg ){
			if( ra_vreg_spilled[vreg] == false && mode == USE){
				regSpillIn( vreg , i );
				ra_vreg_spilled[vreg] = true;
			}
			ra_reg_table[i].inst = vinst_seq;
			return i;
		}
	}				

	XTInt32 max_next = -1;
	XTRegNum max_ps = ra_num_of_reg;

	for( XTRegNum i = 0 ; alloc == ra_num_of_reg  && i < ra_num_of_reg ; i++ ){
		if( ra_reg_table[i].status == FREE ){
			alloc = i;
			break;
		}
	}

	for( XTRegNum i = 0 ; alloc == ra_num_of_reg  && i < ra_num_of_reg ; i++ ){
		if( ra_reg_table[i].status == FREE ){
			alloc = i;
			break;
		}
		else if( ra_reg_table[i].status == ALLOCATED ){
			if( ra_reg_table[i].inst == vinst_seq){
				continue;
			}
			XTRegNum  temp_reg = ra_reg_table[i].mapped_to;
			while( ra_vreg_used_list[temp_reg].empty() == false && 
					ra_vreg_used_list[temp_reg].front().first < vinst_seq ){
				ra_vreg_used_list[temp_reg].pop();
			}
			if( ra_vreg_used_list[temp_reg].empty() || 
					ra_vreg_used_list[temp_reg].front().second == DEF ){
				alloc = i;
				break;
			}
			else if( ra_vreg_used_list[temp_reg].front().first > max_next ){
				max_next = ra_vreg_used_list[temp_reg].front().first;
				max_ps = i;
			}
		}
	}

	if( alloc == ra_num_of_reg ) alloc = max_ps;
	if( alloc == ra_num_of_reg) UTIL::XTLOG("ERROR, There is no physical register could be allocated\n");

	if( ra_reg_table[alloc].status == ALLOCATED ){
		XTRegNum temp_reg = ra_reg_table[alloc].mapped_to;
		if( ra_vreg_used_list[temp_reg].empty() == false && 
				ra_vreg_used_list[temp_reg].front().second == USE ){
			regSpillOut(alloc);
		}						
		ra_vreg_spilled[temp_reg] = false;
	}	
	if( mode == USE ) {
		regSpillIn(vreg,alloc);
		ra_vreg_spilled[vreg] = true;
	}

	ra_reg_table[alloc].mapped_to = vreg;
	ra_reg_table[alloc].inst = vinst_seq;
	ra_reg_table[alloc].status = ALLOCATED;
	return alloc;
}


void NextUseRegAllocator::unmapIfNoNextUse(XTRegNum vreg)
{

}

//NOTICE : As regAllocForce just allocate the expect physical reg to vreg , and 
XTRegNum NextUseRegAllocator::regAllocForce(XTRegNum vreg, XTRegNum expect, RegAccessMode mode)
{
	//printf("This is regAllocForce calling!\n");
	if( ra_reg_table[expect].status == RESERVED ){
		UTIL::XTLOG("Can't force allocate the expect reg to vreg\n");
		return -1;	
	}else if( ra_reg_table[expect].status == ALLOCATED ){
		if( ra_reg_table[expect].mapped_to == vreg ){
			ra_reg_table[expect].inst = vinst_seq;
			if( ra_vreg_spilled[vreg] == false && mode == USE ){
				regSpillIn( vreg , expect );
				ra_vreg_spilled[vreg] = true;
			}
			return expect;
		}else{
			XTRegNum temp_reg = ra_reg_table[expect].mapped_to;
			while( ra_vreg_used_list[temp_reg].empty() == false 
					&& ra_vreg_used_list[temp_reg].front().first < vinst_seq ){
				ra_vreg_used_list[temp_reg].pop();
			}
			if( ra_vreg_used_list[temp_reg].empty() == false
					&& ra_vreg_used_list[temp_reg].front().second == USE ){
				ra_reg_table[expect].status = RESERVED;	
				XTRegNum alloc = regAlloc( temp_reg , DEF );
				(*ra_cb_reg_to_reg)( expect , alloc );
				ra_reg_table[alloc].inst = vinst_seq - 1;	
				ra_reg_table[expect].status = ALLOCATED;	
				//					regSpillOut( expect );
			} else {
				ra_vreg_spilled[temp_reg] = false;
			}
		}
	}
	for( XTRegNum i = 0 ; i < ra_num_of_reg ; i++ ){
		if( ra_reg_table[i].status == ALLOCATED && ra_reg_table[i].mapped_to == vreg ){
			(*ra_cb_reg_to_reg)( i , expect );
			ra_reg_table[expect].status = ALLOCATED;
			ra_reg_table[expect].inst = vinst_seq;
			ra_reg_table[expect].mapped_to = vreg; 
			ra_reg_table[i].status = FREE;
			return expect;	
		}
	}

	ra_vreg_spilled[vreg] = false;
	if( mode == USE ) {
		regSpillIn( vreg , expect );
		ra_vreg_spilled[vreg] = true;
	}
	ra_reg_table[expect].status = ALLOCATED;
	ra_reg_table[expect].mapped_to = vreg;
	ra_reg_table[expect].inst = vinst_seq;
	return expect;
}

/**
 * allocate a physical register in for vreg, the allocated register "R" must satisfy that : (reg_mask & ( 1 << R )) != 0
 * 
 * reg_mask : the allocable physical registers set in binary format. 
 */
XTRegNum NextUseRegAllocator::regAllocExpect(XTRegNum vreg, XTUint8 reg_mask, RegAccessMode mode){
	XTRegNum exist = ra_num_of_reg;
	for( XTRegNum i = 0 ; i < ra_num_of_reg ; i++ ){
		if( ra_reg_table[i].status == ALLOCATED && ra_reg_table[i].mapped_to == vreg ){
			exist = i;
			break;
		}
	}
	if( exist != ra_num_of_reg ) {
		if( reg_mask & ( 1 << exist )){
			ra_reg_table[exist].inst = vinst_seq;
			if( ra_vreg_spilled[vreg] == false && mode == USE ){
				regSpillIn( vreg , exist );
				ra_vreg_spilled[vreg] = true;
			}
			return exist;
		} else {
			XTInt32 temp_status[8];
			for( int i = 0 ; i < ra_num_of_reg ; i ++ ) {
				temp_status[i] = ra_reg_table[i].status;
				if( (reg_mask & ( 1 << i )) == 0 ) {
					ra_reg_table[i].status = RESERVED;
				}
			}
			XTRegNum res = regAlloc( vreg , DEF );
			for( int i = 0 ; i < ra_num_of_reg ; i++ ) {
				if( (reg_mask & ( 1 << i )) == 0 ){
					ra_reg_table[i].status = temp_status[i];
				}
			}
			while( ra_vreg_used_list[vreg].empty() == false 
					&& ra_vreg_used_list[vreg].front().first < vinst_seq ){
				ra_vreg_used_list[vreg].pop();
			}
			if( ra_vreg_used_list[vreg].empty() == false && ra_vreg_used_list[vreg].front().first == vinst_seq    
					&& ra_vreg_used_list[vreg].front().second == USE ){
				(*ra_cb_reg_to_reg)( exist , res );
				ra_vreg_spilled[vreg] = true;
			} else {
				ra_vreg_spilled[vreg] = false;
			}
			ra_reg_table[exist].status = FREE;
			return res;
		}
	} else {
		XTInt32 temp_status[8];
		for( int i = 0 ; i < ra_num_of_reg ; i ++ ) {
			temp_status[i] = ra_reg_table[i].status;
			if( (reg_mask & ( 1 << i )) == 0 ) {
				ra_reg_table[i].status = RESERVED;
			}
		}
		XTRegNum res = regAlloc( vreg , mode);
		for( int i = 0 ; i < ra_num_of_reg ; i++ ) {
			if( (reg_mask & ( 1 << i )) == 0 ){
				ra_reg_table[i].status = temp_status[i];
			}
		}
		return res;
	}

}

XTRegNum NextUseRegAllocator::regAllocForceExcept(XTRegNum vreg, XTRegNum except, RegAccessMode mode)
{
	//  printf("This is regAllocForceExcept calling!\n");
	XTInt32 temp = ra_reg_table[except].status;	
	if( temp == ALLOCATED && ra_reg_table[except].mapped_to == vreg ){
		ra_reg_table[except].status = RESERVED;
		XTRegNum alloc = regAlloc( vreg , DEF );
		if( mode == USE ){
			(*ra_cb_reg_to_reg)( except , alloc );
			ra_vreg_spilled[vreg] = true;
		}		
		ra_reg_table[except].status = FREE;
		return alloc;
	}
	ra_reg_table[except].status = RESERVED;
	XTRegNum alloc = regAlloc( vreg , mode );
	ra_reg_table[except].status = temp;
	return alloc;
}

void NextUseRegAllocator::regAllocReserve(XTRegNum treg)
{
	//printf("This is regAllocReserve calling!\n");
	if(  ra_reg_table[treg].status != ALLOCATED ){
		ra_reg_table[treg].status = RESERVED;
		return ;
	}
	XTRegNum vreg = ra_reg_table[treg].mapped_to;
	if( ra_reg_table[treg].inst == vinst_seq ){
		assert( 0 &&"Can't reserve the reg allocated in the same vinst_seq\n");
	}
	while( ra_vreg_used_list[vreg].empty() == false 
			&& ra_vreg_used_list[vreg].front().first < vinst_seq ){
		ra_vreg_used_list[vreg].pop();
	}
	if( ra_vreg_used_list[vreg].empty() == false   
			&& ra_vreg_used_list[vreg].front().second == USE ){
		regSpillOut( treg );
		ra_vreg_spilled[vreg] = false;
	}
	ra_reg_table[treg].status = RESERVED;
}

void NextUseRegAllocator::regAllocRelease(XTRegNum treg)
{
	// printf("This is regAllocRelease calling!\n");
	ra_reg_table[treg].status = FREE;
}

XTRegNum NextUseRegAllocator::regSpillOut(XTRegNum physical_reg)
{
	XTRegNum vreg = ra_reg_table[physical_reg].mapped_to;
	// assume the source register num is 32 , like mips 
	if( vreg <= 31 ) {
		(*ra_cb_spill_out)(physical_reg,(XTMemAddr)(source_regs+vreg));
	} else {
		(*ra_cb_spill_out)(physical_reg,(XTMemAddr)(ra_spill_pool+vreg));
	}
	return physical_reg;
}

void NextUseRegAllocator::regSpillIn(XTRegNum vreg , XTRegNum treg)
{
	if( vreg <= 31 ) {
		(*ra_cb_spill_in)((XTMemAddr)(source_regs+vreg), treg);
	} else {
		(*ra_cb_spill_in)((XTMemAddr)(ra_spill_pool+vreg), treg);
	}
}
